function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

// 插入排序
var insertSort = function (head) {
    if (head == null || head.next == null) return head;
    const dummy = new ListNode(0);
    dummy.next = head;
    let lastSorted = head;
    let current = head.next;
    while (current != null) {
        if (lastSorted.val <= current.val) {
            lastSorted = lastSorted.next;
        } else {
            let prev = dummy;
            while (prev.next.val <= current.val) {
                prev = prev.next;
            }
            lastSorted.next = current.next;
            current.next = prev.next;
            prev.next = current;
        }
        current = lastSorted.next;
    }
    return dummy.next;
}


// 归并排序
var listSort = function (head) {
    if (head == null || head.next == null) return head;
    return listPartSort(head, null);
}

function listPartSort(head, tail) {
    if (head == null) return head;
    if (head.next == tail) {
        head.next = null;
        return head;
    }
    let slow = head;
    let fast = head;
    while (fast != tail) {
        fast = fast.next;
        slow = slow.next;
        if (fast != tail) {
            fast = fast.next;
        }
    }
    let middleNode = slow;
    let list1 = listPartSort(head, middleNode);
    let list2 = listPartSort(middleNode, tail);
    let root = mergeList(list1, list2);
    return root;
}

function mergeList(list1, list2) {
    const dummy = new ListNode(-1);
    let pre = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            pre.next = list1;
            list1 = list1.next;
        } else {
            pre.next = list2;
            list2 = list2.next;
        }
        pre = pre.next;
    }
    pre.next = list2 == null ? list1 : list2;
    return dummy.next;
}